﻿/*
* 
*	题目70：爬楼梯
	假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

	每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
*/

/*
    方法1：利用数学的排列组合 看一下解法里面有多少个2，进行排列组合
*/
//排列组合 阶乘: C(n,k)
int jiecheng(int n, int k)
{
    if (k == 0 || k == n)return 1;
    if (k > n - k)
    {
        k = n - k;
    }
    long int result = 1;
    for (int i = 1; i <= k; i++)
    {
        result = result * (n - i + 1) / i;
    }
    return result;
}
int climbStairs(int n)
{
    int count = 0;
    int max = n / 2;
    for (int k = 0; k <= max; k++)
    {
        count = count + jiecheng(n - k, k);
    }
    return count;
}


/*
    方法2：动态规划
    我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

    f(x)=f(x−1)+f(x−2)

    它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

*/

int climbStairs(int n) {
    int p = 0;
    int q = 0;
    int r = 1;
    for (int i = 1; i <= n; ++i)
    {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}